package leetcode;

import java.util.HashMap;

/**
 * @author Liangyaoyun
 */
public class leetCode106 {
    public class TreeNode{
        int val;
        TreeNode root;
        TreeNode left;
        TreeNode right;
        TreeNode(){};
        TreeNode(int val){
            this.val=val;
        }
        TreeNode(int val,TreeNode left,TreeNode right){this.val = val;
         this.left = left;
         this.right = right;
        }
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        TreeNode root=new TreeNode(postorder[0]);
        if (inorder.length==1){
            return root;
        }
        return BuildTree(inorder,0,inorder.length-1,postorder,0, postorder.length-1);
    }
    public TreeNode BuildTree(int[] inorder,int inStart,int inEnd,int[] post,int postStart,int postEnd){
        if (inStart>inEnd||postStart>postEnd){
            return null;
        }
        TreeNode root=new TreeNode();
        root.val=post[postEnd];

        int rootIndex=findTreeNode(root,inorder,inStart,inEnd);

        int leftLength=rootIndex-inStart;
        int rightLength=inEnd-rootIndex;

        //在中序数组中，根据 左 根 右 来进行区分左右子树
        //中序:所以左子树的边界就是根节点下标减一,右子树的起点就是根节点加一
        //后序:对于后序来说,起点不变,边界是起点加上左子树长度-1
        root.left=BuildTree(inorder,inStart,rootIndex-1,post,postStart,postStart+leftLength-1);
        //中序:右子树的起点就是根节点下标加一,边界不变
        //后序:起点应该是起点下标加左子树长度,边界要减一
        root.right=BuildTree(inorder,rootIndex+1,inEnd,post,postStart+leftLength,postEnd-1);
        return root;


    }

    public int findTreeNode(TreeNode root,int[] inOrder,int inStart,int inEnd){
        for (int i = inStart; i <=inEnd ; i++) {
            if (root.val==inOrder[i]){
                return i;
            }
        }
        return -1;
    }
}
